package com.lowang.guava.test;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author Lo&Wang
 */
public class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode(' ');
    }

    public TrieNode insert(String word) {
        TrieNode node = search(word);
        if (node != null) {
            node.setCount(node.getCount() + 1);
            return node;
        }
        TrieNode cur = root;
        TrieNode first = null;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            TrieNode child = cur.subNode(c);
            if (child == null) {
                child = new TrieNode(c);
                child.setCount(1);
                cur.children.add(child);
                cur = child;
            }
            cur.setLength(cur.getLength() + 1);
            if (i == 0) {
                first = cur;
            }
        }
        cur.setEnd(true);

        return first;
    }

    public TrieNode search(String word) {
        TrieNode cur = root;
        TrieNode first = null;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            cur = cur.subNode(c);
            if (cur == null) {
                return null;
            }
            if (i == 0) {
                first = cur;
            }
        }
        return cur.isEnd() ? first : null;
    }

    public boolean exist(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            cur = cur.subNode(c);
            if (cur == null) {
                return false;
            }
        }
        return cur.isEnd();
    }

    public static void main(String[] args) {
        Trie tree = new Trie();
        tree.insert("wanghao");
        tree.insert("wanghao");
        System.out.println(tree.exist("wanghao"));
        System.out.println(tree.search("wanghao").getCount());
        
        Map<String,String> map = new LinkedHashMap<String, String>(5);
        map.put("123", "123");
        map.put("1234", "123");
        map.put("12345", "123");
        map.put("123456", "123");
        map.put("1234567", "123");
        map.put("12345678", "123");
        map.put("12345679", "123");
        System.out.println(map.get("12345679"));
    }
}
